#include <stdio.h> 
#include <stdlib.h> 
#define M 3//设置队列总数 
#define N 10//设置进程总数   
typedef struct pcb{  
	int id;//进程号
	int intime;//提交时间
	int priority;//优先级
	int starttime;//开始执行时间
	int length;//进程长度大小
	int endtime;//结束时间
	char state;//状态
	int ptime;//时间片
	struct pcb *next;
 }*PCB,pcb;//进程控制块
   PCB CreatReady(PCB R,int i){
	   R=(PCB)malloc(sizeof(pcb));
	   R->id=i;  R->priority=5-i;
	   R->ptime=i+1;  R->state='R';
	   R->next=NULL;
	   printf("第%d级：\t%d\t%d\n",R->id,R->priority,R->ptime);
	   return R;
   }
   PCB CreatWait(PCB W){
	   int i;
	   pcb *p,*q;
	   q=W;
	   printf("给进程初始化如下(tab键隔开)：\n");
	   printf("进程\tin时间\t优先级\t长度\n");
	   for(i=0;i<N;i++){
		   p=(PCB)malloc(sizeof(pcb));
		   p->next=NULL; 
		   p->id=i+1;
		   printf("P%d\t",p->id);
		   scanf("%d\t%d\t%d",&p->intime,&p->priority,&p->length);
		   q->next=p;
		   q=p;
	   }
	   return W;
   }
   void Insert(PCB R,pcb *cp){
	   pcb *tail;
	   tail=R;
	   while(tail->next){
		   tail=tail->next;
	   }
	   tail->next=cp;
	   cp->next=NULL;
   }
   int FindQuery(PCB R[M]){
	   int i,j;
	   for(i=0;i<M;i++){
		   if(R[i]->next){
			   j=i;break;
		   }
		   else
			   printf("第%d级就绪队列为空\n",R[i]->id);
	   }
	   return j;
   }
   int Dispatch(PCB R,pcb *cp,PCB W,int time,pcb *tp){
	   int s;
	   pcb *p,*phead;
	   phead=W;
	   p=W->next;
	   cp->starttime=time;
	   cp->length-=R->ptime;
	   cp->endtime=cp->starttime+R->ptime;
	   if(cp->length<=0){
		   s=1;//表示完成
		   cp->endtime+=cp->length;
	   } 
	   else{ 
		   if(p){
			   while(p){
				   if((p->intime<cp->endtime)&&(p->priority>cp->priority)){
					   tp->id=p->id;
					   tp->intime=p->intime;
					   tp->length=p->length;
					   tp->priority=p->priority;
					   tp->state=p->state;      //将抢占进程p备份到tp中
					   phead->next=p->next;//从后备队列中删除抢占的进程
					   cp->length +=cp->endtime-tp->intime;
					   cp->endtime-=cp->endtime-tp->intime;
					   s=-1;//表示被抢占
					   break;
				   }
				   else
					   if(p->intime>=cp->endtime){
						   s=0;//在后备队列中没有可以抢占的进程时
						   break;
					   }
					   p=p->next;phead=phead->next;
			   }//查找可以抢占cpu的优先级高的进程tp
		   }
		   else s=0;//在后备队列没有进程时
	   }
	   return s;
   }
   void Print(PCB F){
	   pcb *p;
	   p=F->next;
	   while(p){
		   printf("P%d\t结束时间：%d\n",p->id,p->endtime);
		   p=p->next;
	   }
   }
   PCB MFQ(PCB W,PCB R[M],PCB F){
	   pcb *cp;//当前系统操作的进程
	   pcb *tp;//抢占cpu的进程
	   tp=(PCB)malloc(sizeof(pcb));
	   tp->priority=0;
	   tp->next=NULL;
	   int time=0;//time表示系统当前时间 
     int Finish=0;
	 int i,have,j;
	 int s;
	 while(Finish<N){
		 cp=W->next;
		 if(cp&&cp->intime<=time){
			 have=1;
		 }
		 else
			 have=0;   //判断当前时刻有无进程被提交
		 if(have){
			 i=0;
			 W->next=cp->next;//从后备队列中删除cp
			 Insert(R[0],cp);
			 cp->priority=R[0]->priority;
			 cp->state=R[0]->state;
			 cp=R[0]->next;
			 printf("%d时,P%d被提交入就绪队列%d\n",time,cp->id,R[0]->id);
		 }//将新进程入第一级就绪队列
		 else{
			 i=FindQuery(R);//循环查找不为空的就绪队列
			 cp=R[i]->next;
			 printf("%d时,无可以提交的进程，因此转到就绪队列%d执行P%d\n",time,R[i]->id,cp->id);
		 }
		 s=Dispatch(R[i],cp,W,time,tp);//cpu执行进程，并生成三种结果
		 if(s==1){
			 R[i]->next=cp->next;//从就绪队列中删除已完成的进程
			 Insert(F,cp);
			 Finish++;
			 printf("%d时，P%d处理完成！\n",cp->endtime,cp->id); 
		 }   
		if(s==0){
			if(i<2)
				j=i+1;
			else
				j=i;
			R[i]->next=cp->next;//从就绪队列中删除时间片耗尽的进程
			Insert(R[j],cp);
			cp->priority=R[j]->priority;
			printf("%d时，P%d因时间片耗尽进入下一级就绪队列%d！\n",cp->endtime,cp->id,R[j]->id);
		}
		if(s==-1){
			R[i]->next=cp->next;
			
       Insert(R[i],cp);
	   tp->next=R[0]->next;R[0]->next=tp;
	   tp->priority=R[0]->priority;tp->state=R[0]->state;    //将抢占cpu的进程进入第一级就绪队列并首先执行
	   printf("%d时，P%d被P%d抢占cpu并转入就绪队列%d队尾！\n",cp->endtime,cp->id,tp->id,R[i]->id);
		}
		time=cp->endtime;
	 }
	 return F;
   }
   void main (){
	   PCB W;//后备队列
	   PCB R[M];//就绪队列
	   PCB F;//完成队列
	   int i;
	   printf("就绪队\t优先级\t时间片\n");
	   for(i=0;i<M;i++){
		   R[i]=CreatReady(R[i],i);
	   }//创建就绪队列
	   W=(PCB)malloc(sizeof(pcb));
	   W->state='W';
	   W->next=NULL;
	   W=CreatWait(W);
	   //创建后备队列
	   F=(PCB)malloc(sizeof(pcb));
	   F->state='F';
	   F->next=NULL;//创建完成队列
	   F=MFQ(W,R,F);//MFQ算法调度
	   printf("完成队列如下：\n");
	   Print(F);
   }
